\documentclass[twocolumn]{article}
\usepackage{xeCJK}
\usepackage{graphicx}
\usepackage{caption}
\captionsetup{hypcap=true}
\usepackage{color}
\usepackage[colorlinks]{hyperref}
\usepackage{subfigure}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{indentfirst}
\usepackage{bm}
\usepackage{multirow}
\usepackage[ruled]{algorithm2e}

\bibliographystyle{plain}
\definecolor{red}{rgb}{1,0,0}
\newtheorem{theorem}{Lemma}
%opening
\title{置信度加权的线性分类器}
\author{Mark Dredze, Koby Crammer, Fernando Pereira}

\begin{document}

\maketitle

\begin{abstract}
	我们介绍一种置信度加权线性分类器，它将参数置信度信息添加给线性分类器。 在这种情况下，在线学习器同时更新分类参数和对其置信度的估计。 该种在线算法维护参数向量的高斯分布，并借助样本更新分布的均值和协方差。 对一系列NLP任务的实验评估表明，我们的算法比其他最先进的在线和批处理方法要好，在在线情况下学得更快，并且组合到并行训练中，能更好地进行分类。
\end{abstract}
\section{介绍}
	在线学习算法一次操作单个实例，允许快速，简单的更新，对数据做出少量假设， 并在广泛的实际情景中表现良好。在线学习算法在包括分类， 标记和解析等任务的自然语言处理中已经变得尤其受欢迎。在本文中， 我们回顾了受自然语言任务的特殊性所启发而提出的线性分类学习的设计。 特别地，自然语言处理的特征表示具有非常高的维度（从单词和单词组合得到的数百万个特征是常见的）， 并且大多数特征仅在一小部分实例中出现。然而，这些许多罕见的特征在对包含它们的样本进行分类时很重要。 因此，能否利用这些自然语言数据的特殊性来提高在线学习算法中线性分类器的表现是值得研究的。
	
	我们引入了置信度加权（CW）学习，一种新的在线学习方法，可以对每个参数维护置信概率。 低置信度的参数将会更主动地更新。 参数的置信度通过参数向量的高斯分布来表示，每个新的训练实例都会对其进行更新， 以便在更新后的分布下对正确分类该实例的概率达到规定的置信度。 与最新的在线和批量学习算法、快速学习和并行训练后的新的组合并行分类方法相比，我们有更优越的分类精度。
	
	我们首先讨论自然语言数据的特性。 然后我们得出我们的算法并讨论变体。 一系列实验显示了CW学习的经验收益。 我们最后讨论相关工作。
	
\section{在线算法与NLP}
	在自然语言分类任务中，许多不同的特征，其中大部分是二进制的，很少出现，可能是一个特定类的弱指示。 因此，我们具有数据稀疏性以及高维度参数向量，这需要很大的训练集。 对于某些类型的问题，例如标签或解析中的结构化预测，个别实例的大小和处理复杂度使得在主存储器中保留少量的实例也不可行。 这些特殊性使得一次处理单个实例的在线算法与自然语言任务相匹配。处理大量数据对于在线方法来说很简单，这需要观察每个实例一次，并且一次使用单个实例来更新参数向量，尽管在实践中可能需要几次迭代。 此外，大多数在线更新都非常简单，这使它们非常快。
	
	然而，虽然在线算法对大量的特征和实例做的很好，但它们不是为自然语言任务特征的重尾特征分布而设计的。 这种特征分布可能对学习有不利的影响。 使用典型的线性分类训练算法，如感知器或PA算法（Rosenblatt，1958; Crammer等，2006）， 仅在特征出现时才更新二值的特征参数。 因此，出现频率高的特征通常会有更多更新。 类似地，位于数据流前部的特征比后部的特征更能影响分类结果。 这个结果告诉我们可以为常见的特征提供更好的参数估计，而给不常见的特征提供相对不精确的估计。 然而，在大多数在线算法中，这些特征类型之间没有区别。
	
	考虑一个关于情绪分类问题的例子。在这项任务中，对产品的评价被表示为n克（n-gram），目标是将对产品的评价标记为正面或负面的。考虑一个简单正面的评论：“我喜欢这个作者”。在线更新会增加“喜欢”和“作者”的权重。由于这两个都是常用的单词，所以算法会收敛到正确的值， ``喜欢"的权重为正，``作者"为0。现在考虑一个稍微修改的负面例子：``我喜欢这个作者，但是发现这本书是枯燥的。" 由于``枯燥"是一个罕见的特征，算法对该特征的权重估计很差。 更新将减少``喜欢"和``枯燥"的权重。该算法不知道“枯燥”是罕见的，并且改变的行为可能是由于估计不足的特征（``枯燥"）导致的， 而不是常见的好的估计特征（``喜欢"）。此更新错误地修改为``喜欢"， 并且由于``枯燥"这一特征没有足够的负权重，降低了收敛速度。

	此示例演示了不保存以前的实例（在线学习的特性）可能会影响学习。一个简单的解决方案是给在线算法增加附加信息，保存过去的例子。 具体来说，该算法可以为每个特征权重维护一个置信度参数。 例如，假设二进制特征，该算法可以维护每个特征被观察到的次数，或者对于一般的实值特征， 它可以维护每个特征的累积二阶矩。计数或二阶矩越大，每个特征权重的置信度越大。 然后这些估计被用来更新参数。而不是同时更新实例中出现的每个特征的权重， 所以低置信度的权重比高置信度的会更主动地更新。在每次更新时，通过关注那些低置信度的特征，来增加所有被观测到的特征的置信度。 在上面的例子中，更新会减少``枯燥"的权重，但是``喜欢"的权重只有很小的改变，因为算法已经对此参数有很好的估计。
	
\section{线性分类器的在线学习算法}
	在线算法以轮为单位进行操作。 在第一轮，算法接收一个实例$\bm{x}_i\in\mathbb{R}^d$,它应用其当前预测规则来产生预测$\hat{y}_i\in\{-1,+1\}$（用于二进制分类），然后接收真实标签$y_i\in\{-1,+1\}$并计算损失$l(y_i,\hat{y}_i)$，在这篇文章中使用0-1损失，如果$y_i\neq\hat{y}_i$，$l(y_i,\hat{y}_i)=1$；否则$l(y_i,\hat{y}_i)=0$。然后，该算法更新其预测规则并进行到下一轮。
	
	如许多著名算法一样，如感知器和支持向量机，在这篇文章中，我们的预测规则是线性分类器：
	\begin{equation}
		f_{\bm{\omega}}(\bm{x}):	f_{\bm{\omega}}(\bm{x})=\text{sign}(\bm{x}\cdot\bm{\omega})
	\end{equation}
	如果我们固定$\bm{\omega}$的模，我们可以用$\bm{\omega}$来确定$f_{\bm{\omega}}$，在文章的剩余部分中将使用$\bm{\omega}$。
	
	一个样本$(\bm{x},y)$于一个特定分类器的间隔由$y(\bm{\omega}\cdot\bm{x})$给出。 如果分类器正确地预测真正的标签$y$，则间隔的符号是正的。 间隔的绝对值$|y(\bm{\omega}\cdot\bm{x})|=|\bm{\omega}\cdot\bm{x}|$通常被认为是预测的置信度，值越大，说明置信度越高。 我们用$m_i=y_i(\bm{\omega}\cdot\bm{x})$表示第i轮的间隔。
	
	各种线性分类训练算法，包括感知器和线性支持向量机，将$w$限制为输入示例的线性组合。在线算法通常使用这样的更新形式：
	\begin{equation}
		\bm{\omega}_{i+1} = \bm{\omega}_i + \alpha_iy_i\bm{x}_i
		\label{eq2}
	\end{equation}
	其中$\alpha_i$是一个非负系数。
	
	在本文中，我们关注线性分类器的PA更新方式（Crammer等，2006）。 在第$i$个回合中用$\bm{\omega}_i$预测并接收真实标签$y_i$之后，该算法更新预测函数， 使得样本$(\bm{x}	_i,y_i)$在固定大小的间隔之外（可以总是缩放到1）被正确分类：
	\begin{align}
		\begin{split}
			\bm{\omega} = \underset{\bm{\omega}}{\min}&\frac{1}{2}\|\bm{\omega}_i-\bm{\omega}\|^2\\
			\text{s.t.}\quad&y_i(\bm{\omega}\cdot\bm{x})\ge 1	
		\end{split}
		\label{eq3}
	\end{align}
	解\eqref{eq3}可得出\eqref{eq2}的系数：
	\begin{equation*}
		\alpha_i = \max\left\lbrace \frac{1-y_i(\bm{\omega}_i\cdot\bm{x}_i)}{\|\bm{x}_i\|^2},0\right\rbrace 
	\end{equation*}
	Crammer等人（2006）提供了这种形式的算法的理论分析，并且已经被证明在各种应用中都能很好地工作。

\section{分类器的分布}
	我们用均值为$\mu\in\mathbb{R}^d$、标准偏差为$\sigma\in\mathbb{R}^d$的对角高斯分布来对线性分类器的置信度参数建模。$\mu_j$和$\sigma_j$代表我们对特征$j$的参数的知识和认知。$\sigma_j$越小，对均值$\mu_j$就越有信心。为了简化表示，我们使用协方差矩阵$\Sigma\in\mathbb{R}^{d×d}$作为分布参数，它的主对角线上为$σ$、其余位置为0。注意，虽然我们假定稀疏的二值特征，但算法不依赖于该假设。
	
	在概念上，为了对输入实例$\bm{x}$进行分类，我们随机取参数向量$\bm{\omega}\sim\mathcal{N}(\bm{\mu},\Sigma)$，并根据$\bm{\omega}\cdot\bm{x}$的符号预测标签。 参数向量服从多元高斯分布，那么若把间隔看作随机变量，它服从单变量高斯分布：
	\begin{equation*}
		M\sim \mathcal{N}( y_i(\bm{\mu}\cdot\bm{x}_i),\bm{x}_i^\top\Sigma_i\bm{x}_i )
	\end{equation*}
	间隔的平均值是均值的间隔，其方差与$\bm{x}_i$在$\Sigma_i$上投影的长度成比例。由于间隔非负则预测正确，所以预测正确的概率是：
	\begin{equation*}
		Pr_{\bm{\omega}\sim\mathcal{N}(\bm{\mu},\Sigma)}[M\ge0] = Pr_{\bm{\omega}\sim\mathcal{N}(\bm{\mu},\Sigma)}[y_i(\bm{\omega}\cdot\bm{x}_i)\ge0]
	\end{equation*}
	在不引起混淆的情况下，我们忽略对分布参数的显式依赖而直接写作$Pr[y_i(\bm{\omega}\cdot\bm{x}_i)\ge 0]$
	
	\subsection{更新}
	在第$i$轮，算法调整分布，以确保第i个训练样本的正确预测概率不小于置信度超参数$\eta\in[0,1]$：
	\begin{equation}
		Pr[y_i(\bm{\omega}\cdot\bm{x}_i)\ge 0]\ge\eta
	\end{equation}
	根据PA算法的基本原理（Crammer 等，2006），我们使用KL散度算法选择与当前分布$\mathcal{N}(\bm{\mu}_i,\Sigma_i)$最接近的分布。 因此，在第$i$轮上，算法通过解决以下优化问题来设置分布的参数：
	\begin{align}
		(\bm{\mu}_{t+1},\Sigma_{t+1})=\min D_{KL}( \mathcal{N}(\bm{\mu},\Sigma) \| \mathcal{N}(\bm{\mu}_i,\Sigma_i) )\label{eq5} \\
		\text{s.t.}\quad =P[y_i(\bm{\omega}\cdot\bm{x}_i)\ge0] >= \eta
			\label{eq6}
	\end{align}
	按照Boyd和Vandenberghe（2004，第158页），我们现在推演之后的优化问题的目标和约束。我们先从约束\eqref{eq6}开始。如上所述，在分布$\mathcal{N}(\bm{\mu},\Sigma)$下，$(\bm{x}_i,y_i)$的间隔服从均值$\mu_M = y_i(\bm{\mu}\cdot\bm{x}_i)$和方差$\sigma^2_M = x_i^\top\Sigma\bm{x}_i$的高斯分布。因此分类错误的概率如下：
	\[ Pr[M\le0]=Pr\left[ \frac{M-\mu_M}{\sigma_M}\le\frac{-\mu_M}{\sigma_M} \right] \]
	由于$(\sigma_M - \mu_M)/\sigma_M$是一个正态分布随机变量，所以上述概率等于$\Phi(-\mu_M/\sigma_M)$，其中$\Phi$是正态分布的累积函数。 因此，我们可以将\eqref{eq6}重写为：
	\[\frac{\mu_M}{\sigma_M}\le\Phi^{-1}(1-\eta) = -\Phi^{-1}(\eta) \]
	用$\mu_M$与$\sigma_M$的定义代入，然后移项合并同类项，我们得到：
	\[y_i(\bm{\mu}_i\cdot\bm{x}_i)\ge\phi\sqrt{\bm{x}_i^\top\Sigma_i\bm{x}_i}\]
	其中$\phi =\Phi^{-1}(\eta)$
	
	不幸的是，这个限制关于$\Sigma$并不是凸的，所以我们省略掉开方项，把它线性化：
	\begin{equation}
		y_i(\bm{\mu}_i\cdot\bm{x}_i)\ge\phi(\bm{x}_i^\top\Sigma_i\bm{x}_i)
		\label{eq7}
	\end{equation}
	在概念上，这是一个大间隔的约束，其中间隔要求的值通过二次型取决于样本$\bm{x}_i$。
	
	我们现在研究目标函数\eqref{eq5}，两个高斯分布的KL散度可表示为：
	%todo left right split
	\begin{align}
		\begin{split}
			D_{KL}( \mathcal{N}(\bm{\mu}_0,\Sigma_0) &\| \mathcal{N}(\bm{\mu}_1,\Sigma_1) )=\\ 
			&\frac{1}{2}( \log\left( \frac{\det\Sigma_1}{\det\Sigma_0} \right) +\text{Tr}(\Sigma_1^{-1}\Sigma_0) \\
			&+(\bm{\mu}_1-\bm{\mu}_0)^\top\Sigma_1^{-1}(\bm{\mu}_1-\bm{\mu}_0)-d)
			\label{eq8}
		\end{split}
	\end{align}	
	使用上述等式并省略不相关的常数，我们得到以下修正的优化问题：
	\begin{align}
		\begin{split}
			(\bm{\mu}_{i+1},\Sigma_{i+1})=\min\frac{1}{2}&\log\left(\frac{\det\Sigma_i}{\det\Sigma}\right)+\frac{1}{2}\text{Tr}(\Sigma_i^{-1}\Sigma)\\
			&+\frac{1}{2}(\bm{\mu}_i-\bm{\mu})^\top\Sigma_i^{-1}(\bm{\mu}_i-\bm{\mu})\\
			\text{s.t.}\quad &y_i(\bm{\mu}_i\cdot\bm{x}_i)\ge\phi(\bm{x}_i^\top\Sigma_i\bm{x}_i)
			\label{eq9}
		\end{split}
	\end{align}
	优化目标关于$\bm{\mu}$和$\Sigma$同时为凸，约束为线性，因此可以使用任何凸优化的求解方法来解决这个问题。 我们称对应的更新为Variance Exact。 然而，为了提高效率，我们更喜欢一种称为Variance的闭式近似更新。 在这个近似中，我们允许\eqref{eq9}中的$\Sigma_{i + 1}$的解产生（隐式地）一个全矩阵，然后将其映射到对角矩阵， 即丢弃非主对角线上的元素。该优化问题的拉格朗日函数为：
	\begin{align}
		\begin{split}
			\mathcal{L}= & \frac{1}{2}\log\left( \frac{\det\Sigma_i}{\det\Sigma} \right) +\frac{1}{2}\text{Tr}(\Sigma_i^{-1}\Sigma)\\
			&+\frac{1}{2}(\bm{\mu}_i-\bm{\mu})^\top\Sigma_i^{-1}(\bm{\mu}_i-\bm{\mu})\\
			&+\alpha(-y_i(\bm{\mu}\cdot\bm{x}_i)+\phi(\bm{x}_i^\top\Sigma\bm{x}_i))
		\end{split}
		\label{eq10}
	\end{align}
	在最优点一定有：
	\[ \frac{\partial}{\partial\bm{\mu}} = \Sigma_i^{-1}(\bm{\mu}-\bm{\mu}_i)-\alpha y_i\bm{x}_i=0 \]
	假设$\Sigma$非奇异，我们得到：
	\begin{equation}
		\bm{\mu}_{i+1} = \bm{\mu}_i + \alpha y_i\Sigma_i\bm{x}_i
		\label{eq11}
	\end{equation}
	在最优点，还一定有：
	\begin{equation*}
		\frac{\partial}{\partial\Sigma} = -\frac{1}{2}\Sigma^{-1}+\frac{1}{2}\Sigma_i^{-1}+\phi\alpha\bm{x}_i\bm{x}_i^\top=0
	\end{equation*}
	求解$\Sigma^{-1}$得到：
	\begin{equation}
		\Sigma_{i+1}^{-1} = \Sigma_i^{-1}+2\alpha\phi\bm{x}\bm{x}_i
		\label{eq12}
	\end{equation}
	最后，我们根据Woodbury identity (Petersen \& Pedersen, 2007, Eq.135)计算\eqref{eq12}的逆，得到：
	\begin{align}
		\begin{split}
			\Sigma_{i+1} &= (\Sigma^{-1}_i+2\alpha\phi\bm{x}\bm{x}_i^\top)^{-1}\\
						 &=\Sigma_i-\Sigma_i\bm{x}_i\left(\frac{1}{2\alpha\phi}+\bm{x}_i^\top\Sigma_i\bm{x}_i\right)^{-1}\bm{x}_i^\top\Sigma_i\\ &=\Sigma_i-\Sigma_i\bm{x}_i\frac{2\alpha\phi}{1+2\alpha\phi\bm{x}_i^\top\Sigma_i\bm{x}_i}\bm{x}_i^\top\Sigma_i
		\end{split}
		\label{eq13}
	\end{align}
	
	该优化的KKT条件意味着$\alpha=0$，并且不需要更新，或者在更新之后约束\eqref{eq7}取等号。将\eqref{eq11}和\eqref{eq13}代入\eqref{eq7}的等价版本，我们得到：
	\begin{align}
		\begin{split}
		&y_i(\bm{x}_i\cdot(\bm{\mu}_i+\alpha y_i\Sigma_i\bm{x}_i))=\\
		&\phi\left( \bm{x}_i\left(\Sigma_i-\Sigma_i\bm{x}_i\frac{2\alpha\phi}{1+2\alpha\phi\bm{x}_i^\top\Sigma_i\bm{x}_i}\bm{x}_i^\top\Sigma_i \right)\bm{x}_i  \right)
		\end{split}
		\label{eq14}
	\end{align}
	移项，得到：
	\begin{align}
		\begin{split}
			&y_i(\bm{x}_i\cdot\bm{\mu}_i)+\alpha\bm{x}_i^\top\Sigma_i\bm{x}_i = \\
			&\phi\bm{x}_i^\top\Sigma_i\bm{x}_i-\phi(\bm{x}_i^\top\Sigma_i\bm{x}_i)^2\frac{2\alpha\phi}{1+2\alpha\phi\bm{x}_i^\top\Sigma_i\bm{x}_i}
		\end{split}
		\label{eq15}
	\end{align}
	简便起见，在更新之前，令$M_i = y_i(\bm{x}_i\cdot\bm{\mu}_i)$为间隔的均值，$V_i = \bm{x}_i^\top\Sigma_i\bm{x}_i$为间隔的方差。把它们代入\eqref{eq15}，得到：
	\[ M_i+\alpha V_i = \phi V_i-\phi V_i^2\frac{2\alpha\phi}{1+2\alpha\phi V_i} \]
	直接看到这是关于$\alpha$的二次方程。其较小的根始终为负，因此不是有效的拉格朗日乘子。 令$\gamma_i$为其较大根：
	\begin{equation}
		\gamma_i = \frac{-(1+2\phi M_i)+\sqrt{(1+2\phi M_i)^2-8\phi(M_i-\phi V_i)}}{4\phi V_i}
		\label{eq16}
	\end{equation}
	若在更新之前有$M_i-\phi V_i\ge 0$，那么限制\eqref{eq7}是满足的。若$1+2\phi M_i\le 0$，那么有$M_i\le\phi V_i$，并且根据\eqref{eq16}，我们有$\gamma_i>0$。相反，如果$1+2\phi M_i\ge 0$，那么，仍然根据\eqref{eq16}，我们有：
	\begin{align*}
		\begin{split}
			&\gamma_i>0\\
			&\Leftrightarrow\sqrt{(1+2\phi M_i)^2-8\phi()}>(1+2\phi M_i)\\
			&\Leftrightarrow M_i<\phi V_i
		\end{split}
	\end{align*}
	根据以上的KKT条件，$\alpha_i = 0$或\eqref{eq9}取等号。在后一种情况下，\eqref{eq14}成立，因此$\alpha_i=\gamma_i>0$。总而言之，我们已经证明：
	\begin{theorem}
		拉格朗日乘数的最优值为$\alpha_i = \max\{\gamma_i,0\}$。
		\label{th1}
	\end{theorem}
	以上推导得到一个完整的协方差矩阵。 如上所述，我们将它限制为对角矩阵，因此我们将解决方案投影到对角矩阵集合中以得到我们的近似值。 实际上，它相当于如上所述计算$\alpha_i$，但是用以下规则更新而不是\eqref{eq12}：
	\begin{equation}
		\Sigma_{i+1}^{-1} = \Sigma_i^{-1}+2\alpha\phi\text{diag}(\bm{x}_i)
		\label{eq17}
	\end{equation}
	其中$\text{diag}(\bm{x}_i)$是对角线上为$\bm{x}_i$的元素的平方的对角矩阵。
	\begin{algorithm}
		\caption{Variance Algorithm(Approx)}\label{alg1}
		\SetAlgoNoLine
	    \SetKwInOut{Input}{Input}
	    \SetKwInOut{Output}{Output}
	    \SetKw{Kw}{Initialize:}
	    \Input{confidence parameter $\phi=\bm{\Phi}^{-1}(\eta)$\\
	 			initial variance parameter $\alpha>0$}
		\Kw{$\bm{\mu}_1 = \bm{0},\Sigma = \alpha I$}
		
	    \Output{$\bm{\mu}$}
	
		\For{$i=1,2,\dots$}{
			Receive $\bm{x}_i\in\mathbb{R}^d,y_i\in\{-1,+1\}$\\
			Set the following variables:\\
			\quad$\alpha_i$ as in Lemma \ref{th1}\\
			\quad$\bm{\mu}_{i+1} = \bm{\mu}_i + \alpha y_i\Sigma_i\bm{x}_i$ \\
			\quad$\Sigma_{i+1}^{-1} = \Sigma_i^{-1}+2\alpha\phi\text{diag}(\bm{x}_i)$\\
		}
	\end{algorithm}
	\begin{table}[htbp]
		\centering
		\begin{tabular}{ll}
			comp & comp.sys.ibm.pc.hardware\\
				 & comp.sys.mac.hardware\\
			sci	 & sci.electronics\\
				 & sci.med\\
			talk & talk.politics.guns\\
				 & talk.politics.mideast
		\end{tabular}
		\caption{20 Newsgroups binary decision tasks}\label{table1}
	\end{table}
	算法的伪代码在\ref{alg1}中。 从$\Sigma_1$的初始值和更新规则\eqref{eq12}，我们得出结论：$\Sigma_i$的特征值是减小的，但是从来没有显式设定为零，因此协方差矩阵$\Sigma_i$非奇异。
	
\section{评估}
	我们评估了三种流行的NLP数据集的Variance和Variance-Exact算法。 每个数据集包含几个二分类任务，从中我们选择了12个问题， 每个问题都包含样例标签的均衡混合。
	%todo 人名
	\begin{description}
		%todo bagof-words
		\item[20 Newsgroups] 20 Newsgroups包含大约20,000个新闻组消息，分为20个不同的新闻组。 数据集是二进制和多类文本分类以及无监督聚类的热门选择。 按照常规做法，我们通过创建在两个相似组之间选择的二值决策问题从数据集创建二值问题，如表\ref{table1}所示。 每个消息都表示为二进制bagof-words。 对于每个问题，我们选择了1800个实例。
		
		\item[Reuters（路透社）] 路透社第1卷（RCV1v2 / LYRL2004） 包含超过80万手动分类的新闻稿（Lewis等人，2004年）。 每篇文章都包含一个或多个描述其主题，行业和地区的标签。 我们从标签的文档中创建了以下二值决策任务：保险：人寿（I82002）与非人寿险（I82003）， 商业服务：银行（I81000）与财务（I83000）和零售分销：专卖店（I65400） 与混合零售（I65600）。这些区别涉及到相邻的类别，所以它们相当困难。 文献准备和特征提取的细节由Lewis等人提供（2004）。 对于每个问题，我们选择2000个实例，使用一个包含二值特征的单词表示。 
		%todo uni / bi-gram
		\item[Sentiment（情绪）] 我们获得了更大版本的Blitzer等人的情绪多域数据集（2007） 包含6个亚马逊域名（书，DVD，电子，厨房，音乐，视频）的产品评论。  每个领域的目标是将产品评价分为正面或负面。 特征提取遵循Blitzer等（2007）。 对于每个问题，我们选择2000个使用uni/bi-gram计数的实例。
	\end{description}
	每个数据集随机分为10次交叉验证实验。 在数据上的单个随机运行中，对于每个分类任务调整分类参数（CW的$\phi$和PA的$C$）。 每个问题的最终结果是单个问题平均精度的10倍。 使用McNemar检验来计算统计显著性。
	\subsection{实验结果}
	\begin{table*}[htbp]
		\centering
		\begin{tabular}{|cc|c|c|c|c|c|c|}
		\hline
		&task&PA&Variance&Variance-Exact&SVM&Maxent&SGD\\ \hline
		\textbf{20 Newsgroups}&comp&8.90&$\dag\bm{6.33}$&9.63&$\ast7.67$&$\ast7.62$&7.36\\
					 		  &sci&4.22&$\dag\bm{1.78}$&3.3&$\dag3.51$&$\dag3.55$&$\dag4.77$\\
					 &talk&1.57&1.09&2.21&$\bm{0.91}$&$\bm{0.91}$&1.36\\	\hline
		\textbf{Reuters} &Business&17.80& 17.65&17.70&$\star15.64$&$\star\bm{15.10}$&$\star15.85$\\
				&Insurance&9.76&$\ast\bm{8.45}$&9.49&9.19&8.59&9.05\\
				&Retail&15.41&$\dagger\bm{11.05}$&14.14&$\ast12.80$&$\ast12.30$&$\dag14.31$\\ \hline
		\textbf{Sentiment}&books&19.55&$\ast\bm{17.40}$&20.45&$\dag20.45$&$\dag19.91$&$19.41$\\
				 &dvds&19.71&$\bm{19.11}$&19.91&20.09&19.26&20.20\\
				 &eletronics&17.40&$\dag\bm{14.10}$&17.44&$\dag16.80$&$\dag16.21$&$\dag16.81$\\
				 &kitchen&15.64&$\ast\bm{14.24}$&16.35&15.20&14.94&$15.60$\\
				 &music&20.05&$\ast\bm{18.10}$&19.66&19.35&19.45&18.81\\
				 &videos&19.86&$\star\bm{17.20}$&19.85&$\dag20.70$&$\dag19.45$&$\star19.65$\\ \hline
		\end{tabular}
		\caption{在各数据集上，批学习的错误率。 统计显著性（McNemar）是根据PA或批学习对Variance进行测量的。($\ast p=0.05,\star p=0.01,\dagger p=0.001$)}	\label{table2}
	\end{table*}
	我们从PA算法开始，检查我们的Variance和Variance-Exact版本的性能，如上一节所讨论的。 所有这三种算法在上述数据集上运行，每个训练阶段包括训练数据中的五次，这似乎足以产生收敛。 三种算法在所有十二个数据集的测试集上的平均误差如表\ref{table2}所示。
	\begin{figure}[htbp]
		\centering
		\includegraphics[width=225pt]{trans_pic1.bmp}
		\caption{每次迭代之后，在``talk"测试数据集上的精度}\label{fig1}
	\end{figure}
	Variance-Exact实现了与PA相同的性能，每种方法在半数数据集上实现较低的误差。 相比之下，Variance（近似的）显着提高了PA，在所有十二个数据集上实现了较低的误差，其中9个具有统计学意义。
	
	如上所述，即使是批量学习，在线算法也很有吸引力，因为它们简单，并能处理极大数据集。 在批量学习情景中，这些算法在训练数据上运行多次，这比单次学习的性能要差（Carvalho\&Cohen，2006）。 我们的算法有高精度和学习速度，而只需要对训练数据进行较少的迭代。 这种行为可以在图\ref{fig1}中的``talk"数据集中看到，它显示了每次迭代后，PA基线和两个variance算法在测试数据上的精度。Variance显着地提高了PA，它收敛非常快，在第一次迭代时达到了最佳性能。 相比之下，PA得益于对数据的多次迭代; 从第一次到第五次迭代其表现都有明显变化。  在十二个分类任务中，Variance的误差减少了3.7％，而PA在第一次和第五次迭代之间减少了12.4％， 表明多次迭代更有助于PA。该结果还说明了Variance-Exact的行为， 最初打败了PA但没有提高。 事实上，在十二个数据集中的十一个中，Variance-Exact在第一次迭代中打败了PA。 精确更新导致参数积极更新，最终造成算法非常快速地收敛，甚至比Variance更快。 看来，Variance中的近似更新会减少过度训练并产生最佳的精度。
	\subsection{批学习}
	虽然在线算法被广泛使用，但批处理算法仍然是许多任务的首选。 批学习可以通过检查整个数据集来做出全局学习决策，这超过了在线算法的能力。 一般来说，当应用批量算法时，它们的表现会更好。 我们将新的在线算法（差异）与两种标准批学习算法进行比较： 最大分类（McCallum（2002）中最大学习器的默认配置） 和支持向量机(LibSVM(Chang\&Lin，2001))。我们还测试了随机梯度下降（SGD）算法（Blitzer等，2007），它对NLP任务表现良好。 对于在线方法，调整分类参数：Maxent的高斯先验分布，SVM的C和SGD的学习速率。
	
	批学习的结果如表2所示。 如预期的那样，批学习方法往往比PA更好，SVM更好9次，Maxent有11次。 然而，在大多数情况下，Variance比批学习有所改进，12次之中有10次比SVM与Maxtent更好。 这些结果表明，在这些任务中，更快更简单的在线算法效果要好于更慢而复杂的批学习方法。
	
	我们还评估了在线和批学习的常用技术的效果， 包括取平均和TFIDF特征，都不能提高精度。 虽然上述数据集在标签和特征方面是平衡的，但我们还对不平衡标签或特征分布的变体数据集进行了评估， 并从Variance方法中得到了类似的收益。
	\begin{figure}[htbp]
		\centering
		\includegraphics[width=225pt]{trans_pic2.bmp}
		\caption{在路透社（800k）和情绪（1000k）数据集上运行4次的平均结果。  水平线显示在整个训练集上训练的模型的测试精度。  垂直条显示在数据的不相交部分训练的n（10,50,100）分类器的平均性能、 均匀组合或加权组合。 除了路透社数据集上的均匀和加权组合之外，所有改进都具有统计意义。}\label{fig2}
	\end{figure}
	\subsection{大数据集}
	在线算法在训练数据超过可用内存的任务中特别有吸引力。 然而，即使对数据进行单次连续传递对于极大的训练集也是不切实际的， 因此我们可以并行地用数据的不同部分训练出不同模型，并把学习得到的分类器组合成一个分类器。 虽然这通常不能像对所有数据进行训练的单一模型一样，但它是从非常大的训练集中学习的有效方法。
	
	并行训练的平均模型假设每个模型具有模型参数的同样准确的估计。 然而，我们的模型为每个参数提供了一个置信度，从而允许来自多个模型的参数更智能地组合。 具体来说，我们计算组合高斯模型，能最小化使用散度算子D计算得到的各单独分类器的集合C的总的散度：
	\begin{equation}
		\underset{\bm{\mu},\Sigma}{\min}\sum_{c\in C}D( (\bm{\mu},\Sigma) \| (\bm{\mu}_c,\Sigma)_c )
		\label{eq18}
	\end{equation}
	如果$D$是欧几里德距离，这只是各单独模型的均值。 如果$D$是KL散度，则上式的解是各个模型均值的加权组合：
	\[\bm{\mu}=(\sum_{c\in C}\Sigma_c^{-1})^{-1}\sum_{c\in C}\Sigma_c^{-1}\bm{\mu}_c, \Sigma^{-1}=\sum_{c\in C}\Sigma_c^{-1} \]
	
	我们评估PA和我们的方法的单一模型性能。对于我们的方法，我们通过将数据流分为n个不相交的部分来训练n个（10,50,100）模型来评估分类器的组合， 并报告每n个分类器的平均性能， 组合分类器取n组参数（均匀）和使用KL距离（加权）对4次随机运行的测试数据的组合的平均值。
	
	我们评估了在两个数据集上的分类器组合。 从对Blitzer（2007）的所有领域中的产品的评论中提取了百万情绪实例。 虽然大多数评论来自书籍领域，但评论来自各种各样的亚马逊产品类型，主要是积极的。 从路透社语料库，我们为公司标签创建了一对多的分类任务，产生了804,411个实例，其中381,325个被标记为公司。 对于两个数据集，我们创建了四个随机分裂，每个分组具有一百万个训练实例和10,000个测试实例。 通过对5K随机实例的训练和10K的测试进行参数优化。
	
	两个数据集使用非常不同的特征表示。  路透社数据包含288,062个独特特征，会出现在文档中的特征比率为0.36。  相比之下，情绪数据包含13,460,254个独特特征，会出现在文档中的特征比率为13.33。  这意味着路透社的特征在训练期间往往会出现多次，而情绪特征大多只出现一次。
	
	测试组的平均精度见图\ref{fig2}。 对于Reuters数据，单PA模型比Variance有更高的精度，可能是由于出现在文档中的特征比率低。 然而，组合10个Variance分类器达到了最佳性能。 对于sentiment，组合10个Variance分类器超过了PA，但还不如单Variance模型。 在每种情况下，使用均匀或加权来组合单独的分类器，会提高精度。  情绪加权的组合方式比均匀组合更好，而在路透社中，两种方法相同。
	
	最后，我们计算了大数据集上PA和Variance的实际运行时间，以比较每个模型的速度。 虽然Variance更复杂，需要每个实例更多的计算，实际速度与PA相当; 在所有测试中，两种算法的运行时间差别不大。

\section{相关研究}
	使用指定参数的可变学习率的想法在神经网络中有悠久的历史（Sutton，1992）， 尽管我们以前不知道通过考虑特征频率的方式来确定模型。 二阶感知器（SOP）（Cesa-Bianchi et al。，2005）可能是最接近于我们的CW算法。 两者都是维护权值向量和过去训练样本的相关统计量的在线算法。SOP用特征计数来为确定性建模，而CW使用高斯分布为不确定性建模。 CW算法具有概率上的动机，而SOP则基于几何思路。  Shivaswamy和Jebara（2007）在批学习的背景下使用了这种思想。
	
	高斯过程分类（GPC）维护权重向量（原始）或回归值（双重）的高斯分布。 我们的算法使用与GPC中使用的标准贝叶斯更新不同的更新条件（Rasmussen\&Williams，2006，第3章）， 避免了在GPC中逼近后验的挑战性问题。 贝叶斯点机（Herbrich等人，2001）维护与训练数据一致的权重向量的集合， 并使用最能代表该集合的单个线性分类器。 从概念上讲，该集合是权重向量的非参数分布。 其在线版本（Harrington等人，2003）维护有限数量的权重向量，它们同时更新。

	最后，随着可用数据的增长，对于有效处理训练数据的算法的需求越来越大。 与我们类似的方法是增量学习（Bordes\&Bottou，2005）。 极端的情况是使用每个例子一次，不重复，如Carvalho和Cohen（2006）的倍增更新方法。
	\begin{description}
		\item[Conclusion:]我们提出了加权线性分类器，一种基于参数化置信度的NLP问题设计的新学习方法。 该算法维护参数向量的分布; 在线更新既改善了参数估计，也减少了分布的方差。 我们的方法可以通过在线和批处理的方法进行改进，并且在若干个NLP数据集上学习得更快。 此外，我们的新算法允许更智能的分类器组合技术，在并行学习之后可以获得性能的提升。  我们计划探索CW分类器的理论性质和其他方面，如多类和结构化预测任务，以及其他数据类型。
		
		\item[Acknowledgements:]该材料基于国防高级研究计划署（DARPA）根据合同号FA8750-07-D-0185所支持的工作。
	\end{description}
\section{参考文献(略)}

\end{document}
